package graph.maze;

import java.util.Stack;

/**
 * @author : Rookie
 * @description : 深度优先遍历求解迷宫问题
 * @date : 2023/6/7
 */
public class MazeDFS {
    /**
     * 迷宫地图
     */
    private int[][] maze;
    /**
     * 起点坐标
     */
    private int startX,startY;
    /**
     * 终点坐标
     */
    private int endX,endY;
    /**
     * 记录节点是否访问过
     */
    private boolean[][] visited;
    /**
     * 路径栈
     */
    private Stack<Point> path;

    public MazeDFS(int[][] maze,int startX,int startY,int endX,int endY) {
        this.startX = startX;
        this.startY = startY;
        this.endX = endX;
        this.endY = endY;
        this.maze = maze;
        this.visited = new boolean[maze.length][maze[0].length];
        this.path = new Stack<>();
    }

    public void search() {
        dfs(startX,startY);
    }

    private void dfs(int x,int y) {
        if (x < 0 || x >= maze.length || y < 0 || y >= maze[0].length) {
            // 超出边界
            return;
        }
        if (maze[x][y] == 1 || visited[x][y]) {
            // 障碍物或已经访问过
            return;
        }

        //当前节点设置为访问过
        visited[x][y] = true;
        // 入栈当前节点
        path.push(new Point(x,y));

        // 到达终点
        if (x == endX && y == endY) {
            printPath();
            // 打印所有路径 因此要出栈重新搜索
            path.pop();
            visited[x][y] = false;
            return;
        }

        // 搜索上下左右四个方向
        dfs(x + 1, y);
        dfs(x - 1, y);
        dfs(x, y + 1);
        dfs(x, y - 1);

        path.pop();
        visited[x][y] = false;
    }

    private void printPath() {
        System.out.print("路径：");
        path.forEach(point -> {
            System.out.print("(" + point.x + "," + point.y + ")");
        });
        System.out.println();
    }

    public static void main(String[] args) {
        int[][] maze = {
                {0, 0, 0, 0, 0},
                {0, 1, 1, 0, 0},
                {0, 0, 1, 1, 0},
                {0, 1, 0, 0, 0},
                {0, 0, 0, 1, 0}
        };
        MazeDFS mazeDFS = new MazeDFS(maze, 0, 0, 4, 4);
        mazeDFS.search();
    }
}
